#include <iostream>
using namespace std;
struct ListNode {
    int val;
    ListNode* next;
    ListNode() :val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};
/**
 * merge two list in order
*/
ListNode *mergeTwoLists(ListNode *list1, ListNode *list2)
{
    if (list1 == nullptr)   
        return list2;
    if (list2 == nullptr)
        return list1;
    if (list1->val < list2->val)
    {
        list1->next = mergeTwoLists(list1->next, list2);
        return list1;
    }
    else
    {
        list2->next = mergeTwoLists(list1, list2->next);
        return list2;
    }
}
// 递归的简洁写法
ListNode *mergeTwoLists2(ListNode *list1, ListNode *list2) {
    if(list1 == nullptr) return list2;
    if(list2 == nullptr) return list1;
    ListNode *res = (list1->val < list2->val) ? list1 : list2;
    res->next = (list1->val < list2->val) ? mergeTwoLists(list1->next, list2) : mergeTwoLists(list2->next, list1);
    return res;
}

// 迭代合并
ListNode *mergeTwoLists3(ListNode *list1, ListNode *list2) {
    ListNode *head = nullptr;
    ListNode *tail = nullptr;
    while(list1 || list2) {
        ListNode *tmp;
        if(list1 && list2) {
            if(list1->val < list2->val) {
                tmp = new ListNode(list1->val);
                list1 = list1->next;
            }else {
                tmp = new ListNode(list2->val);
                list2 = list2->next;
            }
        }else if(list1) {
            tmp = new ListNode(list1->val);
            list1 = list1->next;
        }else if(list2) {
            tmp = new ListNode(list2->val);
            list2 = list2->next;
        }
        if(tail) {
            tail->next = tmp;
            tail = tail->next;
        }else {
            tail = tmp;
        }
        if(!head) {
            head = tail;
        }
    }
    return head;
}
